The present invention generally relates to a scheduling control system, and more particularly to a technology effective in an application to the scheduling control system in an input buffer type switch, which is defined as one method of constructing a large-scale ATM switch.
With an explosive spread of Internet and an advent of media dealing with large-capacity and high-quality information over the recent years, it has been highly expected to prepare a large-scale communications infrastructure capable of flexibly dealing with the large-capacity data. Then, the concerns are concentrated upon a switch having a capacity as large as several hundreds of giga order to several tera order as a key for actualization thereof.
A basic input buffer type switch (on the left side in FIG. 2) having a unit buffer for every input route, has a problem of HOL (Head of Line) blocking, and it is known that a throughput thereof increases up to approximately 58.6% at the maximum.
As contrivances for avoiding the HOL blocking, as shown in FIG. 3, there have been proposed some systems for scheduling a forwarding right in accordance with a predetermined algorithm by logically dividing an input buffer unit per output route. What is known as one of those systems is a system for executing Request/Acknowledge control between the input and the output. Based on this system, the scheduling process is executed by transferring and receiving the information many times between the input and the output. Further, according to another system for obtaining such a combination as to maximize an I/O combination, complicated arithmetic processes are repeatedly executed for obtaining an optimum combination.
The input buffer unit has logical buffers corresponding to the number of output lines, but has hitherto come to require a leaky bucket counter (LB counter) for QoS (Quality of Service) band control per output line in order to perform the QoS band control. For example, when the number of output lines is 128 and the number of QoS classes is 16, the number of the band control LB counters becomes as large as 2048 pieces.
A system (FIG. 4) for constructing a unit switch in a cross-bar type, a batcher sorter type (FIG. 5) and a batcher/Banyan type (FIG. 6) may be exemplified by way of conventional methods of constructing a large-scale input buffer type switch oriented switch module.
Further, as a cell synchronizing method, there is a method of taking the synchronization of a cell heading by transferring a frame pulse indicating the cell heading and the data in parallel as shown in FIG. 7.
The above-described system involving the use of the Request/Acknowledge control requires repetitive transfers and receipts of the information between the input and output in order to enhance the characteristic, and therefore a high-speed device is needed for completing the processing within a 1-packet time. Further, according to the system for obtaining the maximum combination, the complicated logical operation is needed and is hard to be actualized by hardware.
Moreover, according to the system using simple round robin control for determining the output line in the scheduling process, the respective lines are always equally allocated under the round robin control. Then, there arises a problem of causing a remarkable decline of forwarding delay from a high-load input line if there are forwarding requests from a plurality of lines with different input loads (unequal loads) with respect to one single output line.
Further, in the large-scale switch accommodating a multiplicity of lines, if the LB counter for band control is structured of logics, a quantity of hardware becomes tremendous. Moreover, if constructed by use of a memory, a problem is that it is difficult to access simultaneously within the 1-packet time.
Furthermore, when the large-scale switch is constructed of a plurality of LSIs or packages, there are required inputs/outputs (I/O) between the LSIs or the packages, of which the number is four times the number of cell highways, and the number of I/Os (inputs/outputs) results in a bottleneck.
Further, in the batcher sorter type, the number of I/Os which is twice the number of cell highways may suffice, however, a configuration per block is different. A problem is that there arise necessities for structuring plural types of LSIs or packages because of I/O lengths being different and for making a phase adjustment.
In addition, when the large-scale switch is constructed of the plurality of LSIs or packages, according to the batcher sorter type etc, it is required that the unit switch be inserted in a path on a minimum scale on the occasion of an extension of the switch scale, and hence the paths are required to be re-configured, resulting in such a problem that the system must be stopped when extending the switch scale.
Moreover, when the large-scale switch is constructed of the plurality of LSIs or packages, the switch module is constructed of only the unit sorters, and, for attaining this construction, it is required that the cells having the output line numbers different from each other without being overlapped be always transferred to the switch module from all the input lines. Hence, if there are not the cells that should be forwarded, what is required of the input buffer is to impart dummy output line numbers to idle cells.
As for this point, Japanese Patent Application Laid-Open No.Hei 3-36841 discloses that the input buffer imparts the output line numbers to the idle cells. According to this technology, the input lines corresponding in sequence to the output line numbers are determined. Therefore, a problem is that the above technology can not be applied to a scheduling system in which the input buffer is constructed of a logical queue per output route, and the input lines can not be univocally determined according to such a sequence of the output line numbers as to determine the output route with respect to each input buffer under contention control.
Further, if the switch, the input buffer and the scheduler are structured extending over a plurality of packages, there might occur desynchronization of a cell level between the packages. In the system for transferring the frame indicating the cell heading and the data in parallel as shown in FIG. 7, however, there exists such a problem that asynchronism of the cell level can not be detected.
The present invention was devised in view of the points described above, and therfore, has an object to actualize a scheduling system capable of causing no deterioration of characteristics even under equal and unequal loads, having no necessity for high-speed repetitive scheduling or complicated arithmetic processes, simplifying its structure, and having a processing speed that does not depend upon a device capability.